perm filename BIN[00,BGB]2 blob
sn#111642 filedate 1974-07-17 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00005 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {F3[C<Nα POLYHEDRON INTERSECTION.λ30P50I425,0JCFA} SECTION 5.
C00004 00003 [5.1 Intersection Geometry.]
C00005 00004
C00006 00005
C00011 ENDMK
C⊗;
{F3;[C;<N;α POLYHEDRON INTERSECTION.;λ30;P50;I425,0;JCFA} SECTION 5.
{JCFD} POLYHEDRON INTERSECTION.
{λ10;W250;JAFA}
5.0 Introduction to Polyhedron Intersection.
5.1 Intersection Geometry.
5.2 2-D Partition Sort of Faces, Edges and Vertices.
5.3 Intersection Topology.
5.5 Special Cases.
5.6 Face Convexity.
5.7 Performance.
{λ30;W0;I950,0;JUFA}
[5.0 Introduction to Polyhedron Intersection.]
The polyhderon intersection algorithm consists of two parts:
first there is a geometric part in which all the faces and edges are
compared with each other for potential intersections and second there
is a topological part in which the desired resultant polyhedron
is copied off of the given polyhedra. The result may consist of more
than one polyhedron.
[5.1 Intersection Geometry.]
The geometric part of the polyhedron intersection algorithm
consists of two routines. One routine determines whether a given
edge passes through a given face and the second routine creates a vertex
at the locus where an edge pierces a face.
[5.2 2-D Partition Sort of Faces, Edges and Vertices.]
COMMENT FIXUP1
FIXUP1 places vertex and wing pointers in all the non-surface
edges. A non-surface edge is distinguished by its non-zero ALT link,
and the new vertices are provided with a A as a first edge, PED, if
it be lacking.;
{λ10;JAF3} A←BODY0;
WHILE (A←PED(A)) ≠ BODY0 DO IF (E←ALT(A))≠0 THEN
BEGIN
PVT(A) ←V← ALT(PVT(E)); IF PED(V)=0 THEN PED(V)←A;
NVT(A) ←V← ALT(NVT(E)); IF PED(V)=0 THEN PED(V)←A;
NCW(A) ← ALT(NCW(E));
PCW(A) ← ALT(PCW(E));
NCCW(A) ← ALT(NCCW(E));
PCCW(A) ← ALT(PCCW(E));
END;
{λ3;JUFA}
COMMENT FIXUP2
FIXUP2 wigns together the surface vertex tridedral corners.
Since it is our good luck that all surface vertices are necessarily
trihedral, the edges can be passed to the WING primitive for oriented
linking, in any order. The two surface wings of a surface vertex
were stored in the NED and PED links by MKSURF; the inward wing can
be retrieve as the PED(ALT(U)). Surface vertices are distinguished by
their ALT vertex having his SURBIT on.;
COMMENT FIXUP3
FIXUP3 replaces the alein faces of the result body with
native faces; this is done by scaning the edge ring of the body,
testing the two faces of each edge to see if they belong to the
result body, and if a face doesn't belong it is replaced by a new
one. Face replacement, as ususal, requires clocking around a face
perimeter and changing the appropriate face link in each edge.